#pragma once
#include<vector>
#include<time.h>

void swap(int& a, int& b)
{
	int tmp = a;
	a = b;
	b = tmp;
}


void QuickSort(std::vector<int>& nums, int begin, int end)
{
	if (begin >= end) return;

	int key = (rand() % (end - begin + 1)) + begin;
	int left = begin - 1, right = end + 1, i = begin;
	int tmp = nums[key];
	while (i < right)
	{
		if (nums[i] < tmp)
		{
			swap(nums[++left],nums[i++]);
		}
		else if (nums[i] == tmp)
		{
			i++;
		}
		else
		{
			swap(nums[--right], nums[i]);
		}
	}
	QuickSort(nums, begin, left);
	QuickSort(nums, right, end);

}
